import java.util.Collections;
class Ch1_Array_and_String {
	
	/*
	 * 1.1 Implement an algorithm to determine if a string has all 
	 * unique characters. What if you can not use additional data structures?
	 * O(n) Time and Space complexity
	 */
	public static boolean isUniqueChar(String str) {
		boolean[] char_set = new boolean[256]; // maximun number of unique char: 255
		// int checker = 0; // bit vector
		for (int i=0; i< str.length(); i++){
			int val = str.charAt(i);
 			// System.out.println("val="+checker);
			if(char_set[val]) return false;
			char_set[val] = true;
			
		}
		/* // use bit vector
		for (int i=0; i< str.length(); i++){
			int val = str.charAt(i) - 'a';
			if (( checker & ( 1 << val )) > 0) return false;
			checker |= (1 << val);
 			// System.out.println("val="+checker);
			// if(char_set[val]) return false;
			// char_set[val] = true;
			
		}*/		
		return true;
	} // 1.1 End

	/*
	 * 1.3 Remove duplicate characters in a string
	 */
	public static void removeDupl(String words) {
		if(words==null) return;
		char str[] = words.toCharArray();
		if( str == null ) return;
		int len = str.length;
		if( len < 2 ) return;		
		int tail  = 1; //length of distinct
		
		for ( int i = 1; i < len; ++i ) {
			int j;
			for ( j = 0; j < tail; ++j ) {
				if ( str[i] == str[j] ) break; // if break, j not increment
			}
			System.out.printf("j=%d and tail=%d\n", j, tail);
			if ( j == tail ) {
				str[tail] = str[i];
				++tail;
			}
		}
		for (int i=tail; tail<len;tail++)
		str[tail] = 0;
		System.out.print(str);
	}
	
	public static void removeDuplEff(char[] str) {
		if( str == null ) return;
		int len = str.length;
		if ( len < 2 ) return;
		boolean[] charChk = new boolean[256];

		charChk[str[0]] = true; 
		int tail = 1;
		for ( int i = 1; i < len; ++i) {
			if (!charChk[str[i]]) {
				str[tail] = str[i];
				++tail;
				charChk[str[i]] = true;
				System.out.println((int)str[i]);				
			}
		}
		for (int i=tail; i<len; i++) { // tailor length
			str[i] = 0;
		}
		System.out.println(str);		
	} // 1.3 end 
	
	// 1.4 anagram
	public static boolean anagram1(String s1, String s2) {
		if ( s1.length() != s2.length() )return false;
		int[] letters = new int[256];
		int unique_no = 0;
		int compared_no = 0;
		char[] s1_array = s1.toCharArray();
		
		for ( char c: s1_array ) { // counter number of each char	
			if (letters[c] == 0) ++unique_no;
			++letters[c];
		}
		
		for(int i=0; i<s2.length();i++) {
			int c = (int)s2.charAt(i);
			if (letters[c] == 0) return false;
			--letters[c];
			if(letters[c] == 0) {
				++compared_no;
				if (compared_no == unique_no ) {
					return i == s2.length()-1;
				}
			}
		}
		
		return false;
	} // 1.4 end 
	
	// 1.5 replace space with %20
	public static String replaceSpace1(String str) {
		str = str.replaceAll(" ","%20");
		return str;
	}
	public static void replaceSpace2(char[] str) {
		int length = str.length;
		int spaceCount=0;
		int newLength = 0;
		
		for (int i = 0; i < length; i++) {
			if(str[i] == ' ') {
				spaceCount++;
			}
		}
		newLength = length+spaceCount*2; // ' '-> '%20'
		str[newLength] = '\0';
		for (int i = length -1 ; i>=0; i--) {
			if (str[i] == ' ') {
				str[newLength-1] = '0';
				str[newLength-2] = '2';
				str[newLength-3] = '%';
				newLength = newLength-3;
			} else {
				str[newLength-1]=str[i];
				newLength--;
			}
		}
		
	} // 1.5 end
	
	// 1.7 cell0 MxN Matrix
	public static void setZeros(int[][] matrix){
		int[] row = new int[matrix.length];
		int[] col = new int[matrix[0].length];
		
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[0].length; j++) {
				if(matrix[i][j] == 0) {
					row[i] = 1;
					col[j] = 1;
				}
			}
		}
		
		for (int i=0; i < matrix.length; i++) {
			for (int j=0; j < matrix[0].length; j++) {
				if( row[i] == 1 || col[j] == 1 )
				matrix[i][j] = 0;
			}
		}
		
		// Print out
		for (int i=0; i < row.length; i++) {
			for (int j=0; j < col.length; j++) {
				System.out.print(matrix[i][j]+"");
			}
			System.out.print("\n");
		}		
	} // 1.7 end
	
	// 1.8 substring rotation
	public static boolean isRotation(String s1, String s2) {
		int len = s1.length();
		if ( len == s2.length() && len > 0 ) {
			String s1s1 = s1+s1;
			return isSubString(s1s1, s2);
		}
		return false;
	}
	
	
	public static void main(String[] args) {
		
		// 1.1
			// System.out.println(isUniqueChar("abcd"));
		// end 1.1
		// 1.3
			// String str = "aaabbcabfadb";
			// removeDupl(str);
			// char[] charchk = {'a','a','b','a','a','b','c','b'};
			// removeDuplEff(charchk);
		// end 1.3
		
		// 1.4
			// String s1 = "what a fuck";
			// String s2= "fuck a wath";
			// // System.out.println("s1's length is "+s1.length());
			// System.out.println("Compare two string: "+anagram1(s1,s2));
		// end 1.4
		
		// 1.5
			// String str5 = " 2 de dfl   dff";
			// System.out.println(replaceSpace1(str5));
		// end 1.5
		
		// 1.7
		// int[][] matrix = new int[4][3];
		int[][] matrix = {
			{1,1,0,1},
			{1,1,1,1},
			{0,1,0,1},
			{1,1,1,1},
			{0,0,1,1}
		};
		setZeros(matrix);	
		// end 1.7
		
		
	}
}